package solution;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/*
* 155
* */
public class MinStack {
    /*
    * 代理原始堆栈
    * 利用栈的特巡并且添加新的属性
    * */
    public static class Solution1{
        private long min;
        private Stack<Long> stack;

        /** initialize your data structure here. */
        public Solution1() {
            stack = new Stack<>();
        }

        public void push(int x) {
            if (stack.isEmpty()){
                stack.push(0L);
                min = x;
            }else {
                stack.push(x - min);
                if (x < min){
                    min = x;
                }
            }
        }

        public void pop() {
            if (stack.isEmpty()){
                return;
            }

            long pop = stack.pop();
            if (pop < 0){
                min = min - pop;
            }

        }

        public int top() {
            long top = stack.peek();
            if (top > 0){
                return (int)(top + min);
            }else {
                return (int)min;
            }

        }

        public int getMin() {
            return (int)min;
        }
    }

    /*
    * 使用两个栈
    * */
    public static class Solustion3{
        Deque<Integer> xStack;
        Deque<Integer> minStack;

        public Solustion3() {
            xStack = new LinkedList<Integer>();
            minStack = new LinkedList<Integer>();
            minStack.push(Integer.MAX_VALUE);
        }

        public void push(int x) {
            xStack.push(x);
            minStack.push(Math.min(minStack.peek(), x));
        }

        public void pop() {
            xStack.pop();
            minStack.pop();
        }

        public int top() {
            return xStack.peek();
        }

        public int getMin() {
            return minStack.peek();
        }
    }

    /*
    * 实现一个新的链表节点
    * */
    public static class Solution2{
        static class Node{
            int value;
            int min;
            Node next;

            public Node(int value, int min) {
                this.value = value;
                this.min = min;
            }
        }
    }

    Solution2.Node head;

    public void push(int x){
        if (head == null){
            head = new Solution2.Node(x, x);
        }else {
            Solution2.Node n = new Solution2.Node(x, Math.min(x, head.min));
            n.next = head;
            head = n;
        }
    }

    public void pop(){
        if (head != null){
            head = head.next;
        }
    }

    public int top(){
        if (head != null){
            return head.value;
        }
        return -1;
    }

    public int getMin(){
        if (head != null){
            return head.min;
        }
        return -1;
    }

}
